package com.wc.alorithm_blue_bridge._思维.最少的1;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @Author congge
 * @Date 2024/4/5 20:38
 * @description https://www.lanqiao.cn/problems/2230/learning/?page=1&first_category_id=1
 */
public class Main {
    static int N = 1000010;
    // a[i] 代表这个数%n的最短路
    static int[] a = new int[N];
    static int n;
    static int INF = 0x3f3f3f3f;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Arrays.fill(a, INF);
        n = sc.nextInt();
        Queue<Integer> q = new LinkedList<>();
        q.add(1 % n);
        q.add(1);
        while (!q.isEmpty()) {
            int t = q.poll();
            int num = q.poll();
            if (a[t] > num) {
                a[t] = num;
                if ((t & 1) == 1) {
                    q.add((t << 1) % n);
                    q.add(num);
                } else {
                    q.add((t << 1) % n);
                    q.add(num);
                    q.add((t + 1) % n);
                    q.add(num + 1);
                }
            }
        }
        System.out.println(a[0]);
    }

}
